package com.lun.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SubsetsII {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
    	List<List<Integer>> result = new ArrayList<>();
    	List<Integer> path = new ArrayList<>();
    	boolean[] used = new boolean[nums.length];
    	Arrays.sort(nums);
    	backtracking(path, nums, used, 0, result);
        return result;
    }
    
    private void backtracking(List<Integer> path, int[] nums, boolean[] used, // 
    		int startIndex, List<List<Integer>> result) {
    	
    	result.add(new ArrayList<>(path));
    	
    	for(int i = startIndex; i < nums.length; i++) {
    		if(i > 0 && nums[i - 1] == nums[i] && !used[i - 1])
    			continue;
    		
    		used[i] = true;
    		path.add(nums[i]);
    		backtracking(path, nums, used, i + 1, result);
    		path.remove(path.size() - 1);
    		used[i] = false;
    	}
    }
    
}
